#include <bits/stdc++.h>
#include "utils.h"

using namespace std;

#define _DEBUG 1

/**
 * @brief 使用回溯算法对输入无重复的向量数据进行全排列
 * 
 * @param state     某次排列已选的有效数据
 * @param choices   原始的无重复向量数据
 * @param selected  某个索引位置的数是否在当前排列中已选择
 * @param res       最终返回的结果数据
 */
void backtrack(vector<int> &state, const vector<int> &choices, 
                vector<bool> &selected, int &count)
{
    // 如果当前序列的长度等于原始向量的长度，表示已经得到一个合适的全排列
    if (state.size() == choices.size()) {
        count++;
        return;
    }

    for (int i = 0; i < choices.size(); i++) {
        bool choice = selected[i];
        if (choice == false) {
            selected[i] = true;
            state.push_back(choices[i]);
            backtrack(state, choices, selected, res);   // 递归

            selected[i] = false;   // 撤销当前选择
            state.pop_back();      //! 尤其注意回溯与DFS的区别
        }
    }
}

/**
 * @brief 对输入的向量数据进行全排列
 * 
 * @param arr 原始向量数据(无重复元素)
 */
void permutation(std::vector<int>& arr) {
    std::vector<int>              state;            // 某次排列已选的有效数据
    int count = 0;
    std::vector<bool> selected(arr.size(), false);  // 指定索引的数据是否已经使用

    backtrack(state, arr, selected, count);

    return;
}


int main() {
    //! 1. 短数据向量
    Vec<int> arr = {1,2,3,4,5};
    auto arr = Vec<int> { 1, 2, 3, 4, 5 };

    //! 2. 长数据向量
    // Vec<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    auto arr = Vec<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    permutation(arr);

    return 0;
}